A FIFO is a memory unit that stores information (referred to as "data items") in such a manner that the data item first in is the data item first out. By way of analogy, an example of a FIFO would be a check-out line at a retail store, wherein the first person to stand in line to purchase goods is the first to be serviced by a cashier.
A FIFO utilizes counters to keep track of data items stored in the FIFO. A FIFO uses a write counter to hold the address for a memory write operation, and a read counter to hold the address for a read operation. Each counter utilizes a count encoding/decoding technique to generate count values. Thus, a write counter generates a write count value, and a read counter generates a read count value.
A FIFO typically compares the write and read count values to determine whether the FIFO is empty or full. The FIFO can accomplish this in a number of different ways. For example, assume a FIFO has six positions numbered 1 through 6. Further assume that positions 1, 2 and 3 are filled with data items. The write counter would be 4 indicating the next position to place a data item in the FIFO. Now assume that data items 1 and 2 were read from the FIFO. The read counter would be 3 indicating the next position to read a data item from the FIFO. The FIFO circuit subtracts the read counter value of 3 from the write counter value of 4 to determine the number of data items left unread from the FIFO, which is 1. Consequently, the FIFO knows that there are 5 positions available in the FIFO to store incoming data items.
The comparison of count values to determine full and empty states of the FIFO is typically accomplished by sending the write count value to the read counter, and vice-versa. This transfer of count values, however, can lead to a problem for some FIFOs. One such FIFO is referred to as a "dual synchronous FIFO."
In a dual synchronous FIFO a problem occurs in comparing a write count value with a read count value. A dual synchronous FIFO utilizes a separate clock signal for each counter. Thus, when comparing count values, a situation arises wherein a count value is generated in one clock domain, and is subsequently sampled in a second clock domain. This asynchronous sampling of count values increases the possibility that the sampling circuit might have the wrong count value due to metastability in the circuit.
Accordingly, conventional dual synchronous FIFOs utilize a count encoding technique ensuring that only one bit changes between consecutive counts to minimize metastability. This count encoding technique is referred to as "Grey encoding/decoding" (Grey encoding). A counter using Grey encoding is typically referred to as a "Grey counter."
The Grey counter, however, is less than satisfactory for a number of reasons. For example, a Grey counter requires complex gating in the underlying hardware. This limits the operational speed of the Grey counter, and therefore the speed at which a device using the FIFO can operate. Further, a Grey counter can only be used for FIFO lengths of 2.sup.N. Thus, for example, a FIFO needed to hold a maximum of 56 data items would have to be allocated 64 data storage registers in order to use a Grey counter. This leads to inefficient use of computer memory.
In view of the foregoing, it can be appreciated that a substantial need exists for a FIFO using a counter that ensures only one bit changes between consecutive count values, and solving the above-discussed problems.